package com.zrf.base.knowledge.leetcode.editor.cn;

import com.google.common.base.Joiner;

import java.util.LinkedList;
import java.util.List;

/**
 * //给定一个 n × n 的二维矩阵表示一个图像。
 * //
 * // 将图像顺时针旋转 90 度。
 * //
 * // 说明：
 * //
 * // 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
 * //
 * // 示例 1:
 * //
 * // 给定 matrix =
 * //[
 * //  [1,2,3],
 * //  [4,5,6],
 * //  [7,8,9]
 * //],
 * //
 * //原地旋转输入矩阵，使其变为:
 * //[
 * //  [7,4,1],
 * //  [8,5,2],
 * //  [9,6,3]
 * //]
 * //
 * //
 * // 示例 2:
 * //
 * // 给定 matrix =
 * //[
 * //  [ 5, 1, 9,11],
 * //  [ 2, 4, 8,10],
 * //  [13, 3, 6, 7],
 * //  [15,14,12,16]
 * //],
 * //
 * //原地旋转输入矩阵，使其变为:
 * //[
 * //  [15,13, 2, 5],
 * //  [14, 3, 4, 1],
 * //  [12, 6, 8, 9],
 * //  [16, 7,10,11]
 * //]
 * //
 * // Related Topics 数组
 * // 👍 622 👎 0
 *
 * @author zhouruifeng
 * @date 2020-11-05 07:46:01
 */
public class RotateImage {
    public static void main(String[] args) {
        Solution solution = new RotateImage().new Solution();
        int[][] matrix = new int[][]{
                new int[]{5, 1, 9, 11},
                new int[]{2, 4, 8, 10},
                new int[]{13, 3, 6, 7},
                new int[]{15, 14, 12, 16}
        };
        solution.rotate(matrix);

        System.out.println("[");
        for (int i = 0; i < matrix.length; i++) {
            int[] tmp = matrix[i];
            System.out.print("[");
            for (int j = 0; j < matrix.length; j++) {
                System.out.print(matrix[i][j] + ",");
            }
            System.out.println("]");
        }
        System.out.println("]");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void rotate(int[][] matrix) {
            int length = matrix.length;
            int maxLayer = (length - 1) / 2;
            for (int i = 0; i <= maxLayer; i++) {
                rotateSingleLayer(matrix, i, maxLayer);
            }
        }

        public void rotateSingleLayer(int[][] matrix, int layer, int maxLayer) {
            if (layer > maxLayer) {
                return;
            }
            int n = matrix.length;
            int endIndex = n - 1 - layer;

            LinkedList<Integer> tmpList = new LinkedList<>();
            int i = layer;
            int j = layer;
            for (; j < endIndex; j++) {
                tmpList.add(matrix[i][j]);
            }
            j = endIndex;
            for (i = layer; i < endIndex; i++) {
                tmpList.add(matrix[i][j]);
            }
            i = endIndex;
            for (j = endIndex; j > layer; j--) {
                tmpList.add(matrix[i][j]);
            }
            j = layer;
            for (i = endIndex; i > layer; i--) {
                tmpList.add(matrix[i][j]);
            }

            int rotateSize = endIndex - layer;
            for (int k = 0; k < rotateSize; k++) {
                tmpList.push(tmpList.pollLast());
            }

            i = layer;
            j = layer;
            for (; j < endIndex; j++) {
                matrix[i][j] = tmpList.pollFirst();
            }
            j = endIndex;
            for (i = layer; i < endIndex; i++) {
                matrix[i][j] = tmpList.pollFirst();
            }
            i = endIndex;
            for (j = endIndex; j > layer; j--) {
                matrix[i][j] = tmpList.pollFirst();
            }
            j = layer;
            for (i = endIndex; i > layer; i--) {
                matrix[i][j] = tmpList.pollFirst();
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}